#include <stdio.h>
#include <stdlib.h>

typedef int ElemType; // 定义元素类型为int
typedef struct LNode
{
  ElemType data;      // 数据域：存储元素值
  struct LNode *next; // 指针域：指向下一个节点
} LNode, *LinkList;   // LNode为节点类型，LinkList为节点指针类型，用于表示链表的头指针

// 1. 初始化链表
/**
 * 初始化链表函数
 * @param L 指向链表头指针的指针，用于返回初始化后的链表头节点
 * 该函数动态分配一个头节点，并将头节点的next指针置为NULL
 */
void InitList(LinkList *L)
{
  // 为头节点分配内存空间
  *L = (LinkList)malloc(sizeof(LNode));
  // 检查内存是否分配成功
  if (*L == NULL)
  {
    printf("内存分配失败!\n");
    return;
  }
  // 将头节点的指针域置为空，表示这是一个空链表
  (*L)->next = NULL;
}
// 创建新节点
LNode *createNode(int val)
{
  LNode *newNode = (LNode *)malloc(sizeof(LNode));
  if (newNode == NULL)
  {
    printf("内存分配失败!\n");
    return NULL;
  }
  newNode->data = val;
  newNode->next = NULL;
  return newNode;
}

// 2. 按位置查找元素，并返回其值
ElemType LocateElem_LL(LinkList L, int pos)
{
  if (pos < 1)
    return -1; // 位置不合法

  LNode *p = L->next; // p指向第一个元素节点
  int j = 1;          // 记录当前是第几个节点

  while (p != NULL && j < pos)
  {
    p = p->next; // 指针后移
    j++;
  }

  if (p == NULL)
    return -1; // 位置超出范围

  return p->data; // 返回找到的元素值
}

// 释放链表内存
void freeList(LNode *head)
{
  LNode *current = head;
  while (current != NULL)
  {
    LNode *temp = current;
    current = current->next;
    free(temp);
  }
}

// 创建带头节点的链表
LinkList createLinkedListWithHead(int values[], int n)
{
  LinkList head;
  InitList(&head); // 创建头节点

  LNode *current = head;
  for (int i = 0; i < n; i++)
  {
    current->next = createNode(values[i]);
    current = current->next;
  }
  return head;
}

/**
 * 打印链表中的所有元素
 * @param L 链表头指针
 */
void printList(LinkList L)
{
  // 检查链表是否存在
  if (L == NULL)
  {
    printf("链表不存在\n");
    return;
  }

  // 定义指针p并指向链表的第一个节点（头结点的下一个节点）
  LNode *p = L->next;
  printf("链表元素: ");
  while (p != NULL)
  {
    printf("%d ", p->data);
    // 移动指针p到下一个节点
    p = p->next;
  }
  printf("\n");
}

int main()
{
  int pos;
  int positions[] = {1, 3, 5, 7, 0, -1};
  LinkList L, L2; // L是链表头指针

  int values[] = {10, 20, 30, 40, 50, 60};
  int values2[] = {70, 80, 90, 100, 110, 120};
  // 初始化链表
  InitList(&L);

  int n = sizeof(values) / sizeof(values[0]);
  int n2 = sizeof(values2) / sizeof(values2[0]);

  LNode *current = L;
  for (int i = 0; i < n; i++)
  {
    current->next = createNode(values[i]);
    current = current->next;
  }

  // 等价于下方的写法
  // L->next = createNode(10);
  // ...
  // L->next->next->next->next->next->next = createNode(60);

  printf("链表元素为: ");
  printList(L);

  // ---------- 新增测试：按位置查找元素 ----------
  int position = sizeof(positions) / sizeof(positions[0]);

  for (int i = 0; i < position; i++)
  {
    ElemType result = LocateElem_LL(L, positions[i]);
    if (result != -1)
    {
      printf("位置 %d 的元素是: %d\n", positions[i], result);
    }
    else
    {
      printf("位置 %d 无效或超出范围\n", positions[i]);
    }
  }

  // 第二种方式：创建带头结点的链表

  L2 = createLinkedListWithHead(values2, n2);

  printf("第二种方式创建的链表元素: ");
  printList(L2);

  // ---------- 新增测试：按位置查找元素 ----------
  for (int i = 0; i < n2; i++)
  {
    ElemType result = LocateElem_LL(L2, positions[i]);
    if (result != -1)
    {
      printf("位置 %d 的元素是: %d\n", positions[i], result);
    }
    else
    {
      printf("位置 %d 无效或超出范围\n", positions[i]);
    }
  }

  // 释放链表内存
  freeList(L);
  freeList(L2);
  return 0;
}